/*
 * @lc app=leetcode.cn id=554 lang=typescript
 *
 * [554] 砖墙
 */

// @lc code=start
function leastBricks(wall: number[][]): number {
  // 记录每行砖块的宽度前缀和，也就是缝隙的位置
  const map: Map<number, number> = new Map();
  for (const width of wall) {
    let sum = 0;
    // 遍历每行砖块宽度，计算前缀和，加入到map中
    // 题目给出不能沿着墙的2边划线，所以最后一块砖不需要遍历
    for (let i = 0; i < width.length - 1; i++) {
      sum += width[i];
      map.set(sum, (map.get(sum) || 0) + 1);
    }
  }

  let maxPrefixSum = 0;
  for (const [_, val] of map.entries()) {
    maxPrefixSum = Math.max(maxPrefixSum, val);
  }
  // 墙的高度减去出现次数最多的前缀和就是结果
  return wall.length - maxPrefixSum;
}
// @lc code=end
